#pragma once
#include <atomic>
// 无锁队列
// 支持写入和读取多线程
template <typename T>
class ThreadLockFreeQueue
{
private:
	struct Node {
		T *data;
		std::atomic<int> hasData;
		std::atomic<Node*> next;
		Node() : data(nullptr), hasData(0), next(nullptr) {
		}
	};
public:
	// 初始化环路
	ThreadLockFreeQueue(int size){
		write = new std::atomic<Node*>();
		read = new std::atomic<Node*>();
		Node* p = new Node();
		write->store(p);
		read->store(p);
		for (int i = 0; i < size; i++) {
			Node* c = new Node();
			p->next = c;
			p = c;
		}
		p->next = write->load();
	};
	// 添加到尾部
	bool AddTail(T *data) {
		Node* oldHead = write->load();
		Node* newNode = oldHead->next;
		// 必须预留一个空位
		if (oldHead->hasData.load() == 1 ||
			newNode->hasData.load() == 1) {
			return false;
		}
		if (write->compare_exchange_weak(oldHead, newNode)) {
			oldHead->data = data;
			oldHead->hasData.store(1);
			return true;
		}
		return false;
	};
	// 获取头部数据
	bool GetFirst(T **data) {
		Node* oldHead = read->load();
		Node* newNode = oldHead->next;
		int old = oldHead->hasData.load();
		if (old == 0) {
			return false;
		}
		if (read->compare_exchange_weak(oldHead, newNode)) {
			*data = oldHead->data;
			oldHead->hasData.store(0);
			return true;
		}
		return false;
	}
private:
	std::atomic<Node*> *write;
	std::atomic<Node*> *read;
};
